package com.xy6.algo.sort;


/**
 * 选择排序
 * 
 * <pre>
 * 时间复杂度：O(n^2)，空间复杂度：n+2
 * 
 * 遍历数组元素[0-n-1]，找到最小元素，与位置0元素交换
 * 遍历数组元素[1-n-1]，找到最小元素，与位置1元素交换
 * 遍历数组元素[2-n-1]，找到最小元素，与位置2元素交换
 * 以此类推，直至待遍历数组元素个数为0
 * 此时，数组所有元素已按从小到大排列
 * </pre>
 * 
 * @author frank
 * @since 2017-06-02
 */
public class SortSelect {

	/**
	 * 输出结果：
	 * 
	 * 1: 1 3 2 2: 1 2 3
	 */
	public static void main(String[] args) {
		int[] arr = new int[] { 3, 1, 2 };
		sort(arr);
	}

	/**
	 * 选择排序
	 * 
	 * @param arr
	 */
	public static void sort(int[] arr) {
		int size = arr.length;
		int temp = 0;
		int min = 0;
		for (int i = 0; i < size - 1; i++) {
			min = i;
			for (int j = i + 1; j < size; j++) {
				if (arr[j] < arr[min]) {
					min = j;
				}
			}
			if (min > i) {
				temp = arr[i];
				arr[i] = arr[min];
				arr[min] = temp;
			}
		}
	}

}
